import java.util.PriorityQueue;

public class Test {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //K个一组翻转链表
    public ListNode reverseKGroup(ListNode head,int k){
        int n = 0;
        ListNode cur = head;
        while(cur!= null){
            cur = cur.next;
            n++;
        }
        n/=k;

        ListNode newHead = new ListNode(0);
        ListNode prev = newHead;
        cur = head;

        for (int i = 0; i < n; i++) {
            ListNode tmp = cur;
            for (int j = 0; j < k; j++) {
                ListNode next = cur.next;
                prev.next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev.next = cur;

        return newHead.next;
    }


    //合并k个升序链表
    //利用堆
    public ListNode mergeKLists(ListNode[] lists){
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2)->v1.val-v2.val);

        for (ListNode l:lists) {
            if (l!= null){
                heap.offer(l);
            }
        }
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while (!heap.isEmpty()){
            ListNode t = heap.poll();
            prev.next = t;
            prev = t;
            if (t.next != null) heap.offer(t.next);
        }
        return ret.next;
    }

    //利用分治递归思想
    public ListNode mergeKList(ListNode[] lists){
        return merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int left, int right){
        if (left>right) return null;
        if (left == right) return lists[left];

        int mid = (left+right)/2;

        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);

        return mergeTwoList(l1,l2);
    }
    public ListNode mergeTwoList(ListNode l1,ListNode l2){
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode newHead = new ListNode(0);
        ListNode cur1 = l1, cur2 = l2 , prev = newHead;

        while (cur1!= null && cur2 != null){
            if (cur1.val <= cur2.val){
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }else{
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }

        if (cur1 != null) prev.next = cur1;
        if (cur2 != null) prev.next = cur2;

        return newHead.next;

    }




    //重排链表
    public  void reorderList(ListNode head){
        if (head == null || head.next == null || head.next.next == null) return;
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode head2 = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;
        while(cur!= null){
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            head2 = head2.next;
        }

        ListNode cur1 = head, cur2 = head2.next;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while (cur1!=null){
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;
            if (cur2 != null){
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }



    //两两交换链表中的节点
    public ListNode swapPairs(ListNode head){
        if (head == null || head.next == null) return head;
        ListNode newHead = new ListNode(0);
        ListNode prev = newHead;
        newHead.next = head;
        ListNode cur = prev.next,next = cur.next,nnext = next.next;
        while(cur!=null && next!=null){
            prev.next = next;
            cur.next = nnext;
            next.next = cur;

            prev = cur;
            cur = nnext;
            if (cur!= null) next = cur.next;
            if (next != null) nnext = next.next;
        }
        return newHead.next;
    }



    //两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2){
        ListNode cur1 = l1,cur2 = l2;
        ListNode newHead = new ListNode(0);
        ListNode prev = newHead;
        int t = 0;
        while(cur1 != null || cur2 != null || t!=0){
            if (cur1 != null){
                t+=cur1.val;
                cur1 = cur1.next;
            }

            if (cur2 != null){
                t+=cur2.val;
                cur2 = cur2.next;
            }
            prev.next = new ListNode(t%10);
            prev = prev.next;
            t/=10;
        }
        return newHead.next;
    }
}
